package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class _15_判断二叉树是否为完全二叉树 {

    public static boolean isCompleteTree(TreeNode root) {

        if (root == null) {

            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        boolean flag = false;
        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();

            TreeNode leftNode = node.left;
            TreeNode rightNode = node.right;

            if ((flag && (leftNode != null || rightNode != null)
                    || leftNode == null && rightNode != null)) {

                return false;
            }

            if (leftNode != null) {
                queue.offer(leftNode);
            }

            if (rightNode != null) {

                queue.offer(rightNode);
            }else {

                flag = true;
            }

        }

        return true;
    }

    public static boolean isCompleteTree01(TreeNode root) {

        if (root == null) {

            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        boolean flag = false;
        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();


            if (flag && (node.left != null || node.right != null)) {

                return false;
            }

            if (node.left != null) {

                queue.offer(node.left);
            } else {

                if (!flag && node.right != null) {

                    return false;
                }
            }

            if (node.right != null) {

                queue.offer(node.right);
            } else {

                if (!flag) {

                    flag = true;
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {

        /**
         *                  6
         *
         *               3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
//        t1.right.left = new TreeNode(7);
//        t1.right.right = new TreeNode(10);

        System.out.println(isCompleteTree(t1));

    }

}
